package done.easy_201_300;

import com.study.common.ListNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

/**
 * 234. Palindrome Linked List  回文链表
 * <p>
 * 请判断一个链表是否为回文链表。
 * <p>
 * 示例 1:
 * 输入: 1->2
 * 输出: false
 * 示例 2:
 * 输入: 1->2->2->1
 * 输出: true
 * 我们使用快慢指针找中点的原理是fast和slow两个指针，每次快指针走两步，慢指针走一步，
 * 等快指针走完时，慢指针的位置就是中点。我们还需要用栈，每次慢指针走一步，都把值存入
 * 栈中，等到达中点时，链表的前半段都存入栈中了，由于栈的后进先出的性质，就可以和后半
 * 段链表按照回文对应的顺序比较了。代码如下：
 *
 * @author wangxiaozhe
 */
@Slf4j
public class PalindromeLinkedList {

    @SuppressWarnings("all")
    public boolean isPalindrome(ListNode head) {
        // 190413 first
        // 190528 first
        // 190529 second
        // 190605 third 忘了，看了答案才做出来
        return true;
    }

    @Test
    public void test() {
        ListNode head = new ListNode(1, 2, 3, 4, 3, 2, 1);
        log.info("result:{}", isPalindrome(head));
    }
}











































/*
public boolean isPalindrome(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    Stack<Integer> stack = new Stack<>();
    while (fast!=null) {
        if (fast.next != null) {
            fast = fast.next.next;
            stack.push(slow.val);
        } else {
            // 偶数
            fast = fast.next;
        }
        slow = slow.next;
    }

    while (slow!=null) {
        if (stack.peek() != slow.val)
            return false;

        stack.pop();
        slow = slow.next;
    }
    return true;
}
*/
